/**
 * 这也是一道动态规划的题目
 * 动态规划的三个重要特性：
 * 1. 最优子结构：最优解的子结构仍然是最优的
 * 2. 无后效性：即某阶段的状态一旦确定，就不会受这个状态以后的状态影响
 * 3.
 * 重叠子问题：我们在使用递归自顶向下处理问题的时候，经常会出现重复计算的问题，有些子问题会被重复计算
 * 动态规划讲这些子问题的计算结果保存在表格中，从而做到以空间换时间
 */
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
  int numTrees(int n) {
    // 其中 dp[i] 用来表示以 1-i 为能组成多少种二叉搜索树
    int dp[21], res = 0;
    memset(dp, 0, sizeof(dp));
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
      for (int j = 1; j <= i; ++j) {
        dp[i] += dp[j - 1] * dp[i - j];
      }
    }
    return dp[n];
  }
};
